﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【学习记录】
//【初阶】29.单链表实现（收尾）
//【初阶】30.OJ题练习
//【初阶】31.休息
//【初阶】32.OJ题练习
//【初阶】33.OJ题练习
//【初阶】34.OJ题练习



//【头文件包含】
#include"SingleList.h"



//【函数声明】
SGLN* reverseSingleList1(SGLN* head);
SGLN* reverseSingleList2(SGLN* head);
SGLN* reverseSingleList3(SGLN* head);
void TestSingleList2();
SGLN* findSingleListMid1(SGLN* head);
SGLN* findSingleListMid2(SGLN* head);
SGLDataType countdownSingleList(SGLN* head, int n);
SGLN* combinSingleList(SGLN* head1, SGLN* head2);



//【主函数】
int main()
{
	//OJ题目练习1
	{
		printf("练习1:给一个链表的头结点head翻转链表返回新链表\n");
		TestSingleList2();
		printf("\n");
	}
	//OJ题目练习2
	{
		printf("练习2:给非空链表的头结点head，返回链表的中间节点，偶数个返回第二个\n");
		//创建链表
		SGLN* plist = NULL;
		SGLN** pplist = plist;
		SingleListPushBack(&plist, 1);
		SingleListPushBack(&plist, 2);
		SingleListPushBack(&plist, 6);
		SingleListPrint(plist);
		//执行函数
		SGLN* ret = findSingleListMid1(plist);
		printf("%d\n", ret->data);
		ret = findSingleListMid2(plist);
		printf("%d\n", ret->data);

		//创建链表
		plist = NULL;
		pplist = plist;
		SingleListPushBack(&plist, 3);
		SingleListPushBack(&plist, 4);
		SingleListPushBack(&plist, 5);
		SingleListPushBack(&plist, 6);
		SingleListPrint(plist);
		//执行函数
		ret = findSingleListMid1(plist);
		printf("%d\n", ret->data);
		ret = findSingleListMid2(plist);
		printf("%d\n", ret->data);

		printf("\n");
	}

	//OJ题目练习3
	{
		printf("练习3:输入链表，输出该链表倒数第k个节点\n");
		//创建链表
		SGLN* plist = NULL;
		SGLN** pplist = plist;
		SingleListPushBack(&plist, 1);
		SingleListPushBack(&plist, 2);
		SingleListPushBack(&plist, 6);
		SingleListPushBack(&plist, 3);
		SingleListPushBack(&plist, 4);
		SingleListPushBack(&plist, 5);
		SingleListPushBack(&plist, 6);
		SingleListPrint(plist);
		//执行函数
		int x = 3;
		SGLDataType ret = countdownSingleList(plist,x);
		printf("%d\n", ret);

		
		printf("\n");
	}

	//OJ题目练习4
	{
		printf("练习4:合并两个有序链表（升序、拼接）\n");
		SGLN* plist = NULL;
		SGLN* plist2 = NULL;
		SingleListPushBack(&plist, 1);
		SingleListPushBack(&plist, 2);
		SingleListPushBack(&plist, 6);
		SingleListPrint(plist);

		SingleListPushBack(&plist2, 3);
		SingleListPushBack(&plist2, 4);
		SingleListPushBack(&plist2, 5);
		SingleListPushBack(&plist2, 6);
		SingleListPrint(plist2);

		SGLN* ret = combinSingleList(plist, plist2);
		SingleListPrint(ret);


		printf("\n");
	}

	return 0;
}



//【函数】}
/*单链表倒置1（原链表操作）*/SGLN* reverseSingleList1(SGLN* head)
{
	if (head == NULL)
		return NULL;
	SGLN* befor = NULL;
	SGLN* cur = head;

	SGLN* next = head->next;

	while (cur)
	{
		cur->next = befor;
		befor = cur;
		cur = next;
		if (next != NULL)
		{
			next = next->next;
		}
	}

	return befor;
}
/*单链表倒置2（新链表头插）*/SGLN* reverseSingleList2(SGLN* head)
{
	SGLN* newhead =NULL ;
	SGLN* cur = head;
	while (cur)
	{
		SingleListPushFront(&newhead, cur->data);
		cur = cur->next;

	}
	SingleListDestory(&head);//销毁原链表空间
	return newhead;
}
/*单链表倒置3（迭代逻辑头插）*/SGLN* reverseSingleList3(SGLN* head)
{
	SGLN* cur = head;
	
	SGLN* newhead = NULL;
	while (cur)
	{
		SGLN* next = cur->next;
		cur->next = newhead;
		newhead = cur;

		cur = next;
	}
	return newhead;
}
/*单链表倒置-测试用例*/void TestSingleList2()
{
	
		SGLN* plist = NULL;
		SGLN** pplist = plist;
		//尾插
		SingleListPushBack(&plist, 1);
		SingleListPushBack(&plist, 2);
		SingleListPushBack(&plist, 6);
		SingleListPushBack(&plist, 3);
		SingleListPushBack(&plist, 4);
		SingleListPushBack(&plist, 5);
		SingleListPushBack(&plist, 6);
		SingleListPrint(plist);
		plist=reverseSingleList1(plist);
		SingleListPrint(plist);
		plist = reverseSingleList2(plist);
		SingleListPrint(plist);
		plist = reverseSingleList3(plist);
		SingleListPrint(plist);


	

	printf("销毁单链表空间\n");
	SingleListDestory(&plist);
	printf("打印检查\n");
	SingleListPrint(plist);

}
/*查找单链表中间节点（快慢指针）*/SGLN* findSingleListMid1(SGLN* head)
{
	SGLN* p1 = head;
	SGLN* p2= head;
	int count = 0;
	while (p2 != NULL)
	{
		p2 = p2->next;
		++count;
		if (count % 2 == 0)
		{
			p1 = p1->next;
		}
	}
	return p1;
}
/*查找单链表中间节点（快慢指针）(标准)*/SGLN* findSingleListMid2(SGLN* head)
{
	SGLN* p1 = head;
	SGLN* p2 = head;
	while (p2&&p2->next)
	{
		p1 = p1->next;
		p2 = p2->next->next;
	}
	return p1;
}

/*输出该链表倒数第k个节点*/SGLDataType countdownSingleList(SGLN* head, int n)
{
	
	SGLN* p1 = head;
	SGLN* p2 = head;
	int i = 1;
	while (p2)
	{
		p2 = p2->next;
		if (i++ > n)
		{
			p1 = p1->next;
		}
	}
	return p1->data;
}
/*合并两个有序链表（升序、拼接）*/SGLN* combinSingleList(SGLN* head1, SGLN* head2)
{
	if (head1 == NULL)
		return head2;
	if (head2 == NULL)
		return head1;
	SGLN* head = NULL;
	SGLN* tail = NULL;
	if (head1->data < head2->data)
	{
		head = tail = head1;
		head1 = head1->next;
	}
	else
	{
		head = tail = head2;
		head2 = head1->next;
	}
	while (head1 && head2)
	{
		if (head1->data < head2->data)
		{
			tail->next = head1;
			tail = head1;
			head1 = head1->next;
		}
		else
		{
				tail->next = head2;
				tail = head2;
			head2 = head2->next;
		}
	}
	if (head1)
	{
		tail->next = head1;
	}
	else if (head2)
	{
		tail->next = head2;
	}
	return head;

}



//【笔记】
//28.单链表实现
	//单链表弊端
		// 单链表更多是做更复杂数据结构的子结构，如哈希桶、邻接表
		// 链表存储数据更应该使用双向链表
	//void SingleListInsert();//单链表指定位置插入 
	//void SingleListErase();//单链表指定位置删除
	//SGLN* SingleListFind();//单链表查找元素
		//先断言链表是否为空，为空则不执行
		//否则从第一个结构体依次查找，直到结构体地址成员为空
		//找到返回对应值所在结构体指针地址
		//否则反会空指针
	//void SingleListDestory();//单链表动态内存空间销毁
